package com.zhang.study.chapter03;


import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Comparator;
import java.util.Stack;

/**
 * 在基本功能的栈基础上，再实现返回栈中最小元素的功能
 * 1. pop、push、getMin操作的时间复杂度都是 O(1)。
 * 2. 设计的栈类型可以使用现成的栈结构
 */
public class Code08_GetMinStack {


    @Data
    @NoArgsConstructor
    public static class MinStack<T> {

        private Stack<T> stackData;
        private Stack<T> stackMin;


        private Comparator<T> comparator;

        public MinStack(Comparator<T> comparator) {
            this.stackData = new Stack<>();
            this.stackMin = new Stack<>();
            this.comparator = comparator;

        }

        // 添加元素到栈中，并更新最小栈
        public void push(T item) {
            stackData.push(item);
            if (stackMin.isEmpty() || comparator.compare(item, stackMin.peek()) <= 0) {
                stackMin.push(item);
            }
        }

        // 弹出栈顶元素，并更新最小栈（如果需要）
        public T pop() {
            T item = stackData.pop();
            if (item.equals(stackMin.peek())) {
                stackMin.pop();
            }
            return item;
        }

        // 获取当前栈中的最小元素
        public T getMin() {
            if (!stackMin.isEmpty()) {
                return stackMin.peek();
            } else {
                throw new RuntimeException("Stack is empty");
            }
        }


    }

    public static void main(String[] args) {
        MinStack<Integer> integerMinStack = new MinStack<>(Comparator.comparingInt(o -> o));
        integerMinStack.push(4);
        integerMinStack.push(3);
        integerMinStack.push(2);
        integerMinStack.push(1);
        System.out.println(integerMinStack.getMin());
        integerMinStack.pop();
        System.out.println(integerMinStack.getMin());


    }

}
